import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/8 10:11
 * @description 使用正负号来标记，遍历到位置i时，判断nums[nums[i]-1]的正负性
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            int x = Math.abs(nums[i]);
            if (nums[x - 1] > 0) {
                // nums[x-1]是正数，说明nums[i]还没有出现过，将其加上负号
                nums[x - 1] = -nums[x - 1];
            } else {
                // 出现过一次，直接加入答案中。
                ans.add(x);
            }
        }
        return ans;
    }
}
